//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
// 示例 4：
//
//
//输入：s = "([)]"
//输出：false
//
//
// 示例 5：
//
//
//输入：s = "{[]}"
//输出：true
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成
//
// Related Topics 栈 字符串 👍 3353 👎 0

package leetcode.editor.cn;

import java.util.Stack;

class 有效的括号 {
    public static void main(String[] args) {
        Solution solution = new 有效的括号().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }
            char[] str = s.toCharArray();
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < str.length; i++) {
                char cha = str[i];
                if (cha == '(' || cha == '[' || cha == '{') {
                    stack.add(cha);
                } else {
                    if (stack.isEmpty()) {
                        return false;
                    }
                    char last = stack.pop();
                    if ((cha == ')' && last != '(') || (cha == ']' && last != '[') || (cha == '}' && last != '{')) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)
    //压栈相反符号  数组替换栈
    public static boolean isValid(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        char[] stack = new char[N];
        int size = 0;
        for (int i = 0; i < N; i++) {
            char cha = str[i];
            if (cha == '(' || cha == '[' || cha == '{') {
                stack[size++] = cha == '(' ? ')' : (cha == '[' ? ']' : '}');
            } else {
                if (size == 0) {
                    return false;
                }
                char last = stack[--size];
                if (cha != last) {
                    return false;
                }
            }
        }
        return size == 0;
    }
}
